package arithmetic2.day13;

import java.util.Arrays;

/**
 * 给定一个数组，每个元素代表一个硬币的面额，求凑成指定的钱最小需要多少枚硬币
 */
public class MinCoinNumber {
    public static void main(String[] args) {
        int arr[] = new int[]{2, 3, 1, 2, 4, 6};
//        int minCoin = minCoin(arr, 0, 10);
//        int minCoin = minCoin2(arr, 0, 10);
        int minCoin = minCoin3(arr, 0, 10);
        System.out.println(minCoin);
    }

    /**
     * 求凑成指定的面额的最少硬币数
     *
     * @param arr:所有硬币的数组
     * @param cur:当前遍历到的硬币
     * @param rest:还需要凑的钱
     * @return
     */
    public static int minCoin(int arr[], int cur, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (rest == 0) {
            return 0;
        }
        //后面没有硬币了,并且rest>0,表示没有解
        if (cur == arr.length) {
            return -1;
        }
        //后面还有硬币,分为两种情况（1.用当前这枚硬币，2.不用当前硬币）
        //1.用当前硬币
        int p1 = minCoin(arr, cur + 1, rest - arr[cur]);
        //2.不用当前硬币
        int p2 = minCoin(arr, cur + 1, rest);
        //上面两种情况都无解
        if (p1 == -1 && p2 == -1) {
            return -1;
        } else {
            if (p1 == -1) {
                return p2;
            } else if (p2 == -1) {
                return p1 + 1;
            }
            //两种情况都有解，取最小值
            return Math.min(p1 + 1, p2);
        }
    }

    //使用记忆化搜索优化递归
    public static int minCoin2(int[] arr, int cur, int rest, int[][] dp) {
        if (rest < 0) {
            return -1;
        }
        if (dp[cur][rest] != -2) {
            return dp[cur][rest];
        }
        if (rest == 0) {
            dp[cur][rest] = 0;
            return dp[cur][rest];
        }
        //后面没有硬币了,并且rest>0,表示没有解
        if (cur == arr.length) {
            dp[cur][rest] = -1;
        } else {
            int p1 = minCoin(arr, cur + 1, rest - arr[cur]);
            int p2 = minCoin(arr, cur + 1, rest);
            if (p1 == -1 && p2 == -1) {
                dp[cur][rest] = -1;
            } else {
                if (p1 == -1) {
                    dp[cur][rest] = p2;
                } else if (p2 == -1) {
                    dp[cur][rest] = p1 + 1;
                } else {
                    dp[cur][rest] = Math.min(p1 + 1, p2);
                }
            }
        }
        return dp[cur][rest];
    }

    public static int minCoin2(int[] arr, int cur, int rest) {
        int[][] dp = new int[arr.length + 1][rest + 1];
        //初始化dp
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], -2);
        }
        return minCoin2(arr, cur, rest, dp);
    }

    //使用动态规划来求解
    public static int minCoin3(int[] arr, int cur, int rest) {
        int[][] dp = new int[arr.length + 1][rest + 1];
        for (int j = 1; j < dp[dp.length - 1].length; j++) {
            dp[dp.length - 1][j] = -1;
        }
        //i遍历cur，j遍历rest
        for (int i = dp.length - 2; i >= 0; i--) {
            for (int j = dp[0].length - 1; j > 0; j--) {
                int p1 = dp[i + 1][j];
                int p2 = -1;
                if (j - arr[i] >= 0) {
                    p2 = dp[i + 1][j - arr[i]];
                }
                if (p1 == -1 && p2 == -1) {
                    dp[i][j] = -1;
                } else if (p1 == -1) {
                    dp[i][j] = p2 + 1;
                } else if (p2 == -1) {
                    dp[i][j] = p1;
                } else {
                    dp[i][j] = Math.min(p1, p2);
                }
            }
        }
        return dp[cur][rest];
    }
}
